{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #3Sum With Multiplicity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #two-pointers #counting #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #双指针 #计数 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: threeSumMulti"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #三数之和的多种可能"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组<meta charset=\"UTF-8\" />&nbsp;<code>arr</code>&nbsp;，以及一个整数&nbsp;<code>target</code>&nbsp;作为目标值，返回满足 <code>i &lt; j &lt; k</code> 且<meta charset=\"UTF-8\" />&nbsp;<code>arr[i] + arr[j] + arr[k] == target</code>&nbsp;的元组&nbsp;<code>i, j, k</code>&nbsp;的数量。</p>\n",
    "\n",
    "<p>由于结果会非常大，请返回 <code>10<sup>9</sup>&nbsp;+ 7</code>&nbsp;的模。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,1,2,2,3,3,4,4,5,5], target = 8\n",
    "<strong>输出：</strong>20\n",
    "<strong>解释：</strong>\n",
    "按值枚举(arr[i], arr[j], arr[k])：\n",
    "(1, 2, 5) 出现 8 次；\n",
    "(1, 3, 4) 出现 8 次；\n",
    "(2, 2, 4) 出现 2 次；\n",
    "(2, 3, 3) 出现 2 次。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,1,2,2,2,2], target = 5\n",
    "<strong>输出：</strong>12\n",
    "<strong>解释：</strong>\n",
    "arr[i] = 1, arr[j] = arr[k] = 2 出现 12 次：\n",
    "我们从 [1,1] 中选择一个 1，有 2 种情况，\n",
    "从 [2,2,2,2] 中选出两个 2，有 6 种情况。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= arr.length &lt;= 3000</code></li>\n",
    "\t<li><code>0 &lt;= arr[i] &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= target &lt;= 300</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [3sum-with-multiplicity](https://leetcode.cn/problems/3sum-with-multiplicity/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [3sum-with-multiplicity](https://leetcode.cn/problems/3sum-with-multiplicity/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,2,2,3,3,4,4,5,5]\\n8', '[1,1,2,2,2,2]\\n5', '[2,1,3]\\n6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        mod, ans = 1000000007, 0\n",
    "        cnts = collections.Counter(arr)\n",
    "        vals = [k for k in cnts]\n",
    "        vals.sort()\n",
    "        n = len(vals)       \n",
    "        for i in range(n):\n",
    "            v1 = vals[i]\n",
    "            for j in range(i, n):\n",
    "                v2, v3 = vals[j], target - v1 - vals[j]\n",
    "                if v3 < v2: break\n",
    "                if v1 == v2 == v3:\n",
    "                    ans = (ans + cnts[v1] * (cnts[v1] - 1) * (cnts[v1] - 2) // 6) % mod\n",
    "                elif v1 == v2:\n",
    "                    ans = (ans + cnts[v1] * (cnts[v1] - 1) * cnts[v3] // 2) % mod\n",
    "                elif v2 == v3:\n",
    "                    ans = (ans + cnts[v1] * cnts[v2] * (cnts[v2] - 1) // 2) % mod\n",
    "                else:\n",
    "                    ans = (ans + cnts[v1] * cnts[v2] * cnts[v3]) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def threeSumMulti(self, A, target):\n",
    "        MOD = 10**9 + 7\n",
    "        ans = 0\n",
    "        A.sort()\n",
    "\n",
    "        for i, x in enumerate(A):\n",
    "            # We'll try to find the number of i < j < k\n",
    "            # with A[j] + A[k] == T, where T = target - A[i].\n",
    "\n",
    "            # The below is a \"two sum with multiplicity\".\n",
    "            T = target - A[i]\n",
    "            j, k = i+1, len(A) - 1\n",
    "\n",
    "            while j < k:\n",
    "                # These steps proceed as in a typical two-sum.\n",
    "                if A[j] + A[k] < T:\n",
    "                    j += 1\n",
    "                elif A[j] + A[k] > T:\n",
    "                    k -= 1\n",
    "                # These steps differ:\n",
    "                elif A[j] != A[k]: # We have A[j] + A[k] == T.\n",
    "                    # Let's count \"left\": the number of A[j] == A[j+1] == A[j+2] == ...\n",
    "                    # And similarly for \"right\".\n",
    "                    left = right = 1\n",
    "                    while j + 1 < k and A[j] == A[j+1]:\n",
    "                        left += 1\n",
    "                        j += 1\n",
    "                    while k - 1 > j and A[k] == A[k-1]:\n",
    "                        right += 1\n",
    "                        k -= 1\n",
    "\n",
    "                    # We contributed left * right many pairs.\n",
    "                    ans += left * right\n",
    "                    ans %= MOD\n",
    "                    j += 1\n",
    "                    k -= 1\n",
    "\n",
    "                else:\n",
    "                    # M = k - j + 1\n",
    "                    # We contributed M * (M-1) / 2 pairs.\n",
    "                    ans += (k-j+1) * (k-j) // 2\n",
    "                    ans %= MOD\n",
    "                    break\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        ans = 0\n",
    "        MOD = int(1e9 + 7)\n",
    "        arr.sort()\n",
    "        for k in range(2, n):\n",
    "            l, r = 0, k - 1\n",
    "            while l < r:\n",
    "                if arr[l] + arr[r] + arr[k] == target:\n",
    "                    i, j = l, r\n",
    "                    if arr[l] == arr[r]:\n",
    "                        ans = (ans + (r - l) * (r - l + 1) // 2) % MOD\n",
    "                        break\n",
    "                    while arr[i] == arr[l]: i += 1\n",
    "                    while arr[j] == arr[r]: j -= 1\n",
    "                    ans = (ans + (i - l) * (r - j)) % MOD\n",
    "                    l, r = i, j\n",
    "                elif arr[l] + arr[r] + arr[k] < target:\n",
    "                    l += 1\n",
    "                else:\n",
    "                    r -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        nums = Counter(arr)\n",
    "        res = 0\n",
    "        keys = sorted(nums.keys())\n",
    "        for i, x in enumerate(keys):\n",
    "            temp = target - x\n",
    "            j, k = i, len(keys) - 1\n",
    "            while j <= k:\n",
    "                if keys[j] + keys[k] < temp:\n",
    "                    j += 1\n",
    "                elif keys[j] + keys[k] > temp:\n",
    "                    k -= 1\n",
    "                else:\n",
    "                    if i < j < k:\n",
    "                        res += nums[x] * nums[keys[j]] * nums[keys[k]]\n",
    "                    elif i == j < k:\n",
    "                        res += nums[x] * (nums[x] - 1) // 2 * nums[keys[k]]\n",
    "                    elif i < j == k:\n",
    "                        res += nums[x] * nums[keys[j]] * (nums[keys[j]] - 1) // 2\n",
    "                    else:\n",
    "                        res += nums[x] * (nums[x] - 1) * (nums[x] - 2) // 6\n",
    "                    j += 1\n",
    "                    k -= 1\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        cnt = Counter(arr)\n",
    "        nums = sorted(list(cnt.keys()))\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "\n",
    "        # 123组合\n",
    "        for i in range(n - 1):\n",
    "            x = nums[i]\n",
    "            for j in range(i + 1, n):\n",
    "                y = nums[j]\n",
    "                z = target - x - y\n",
    "                if z > y:\n",
    "                    ans += cnt[x] * cnt[y] * cnt[z]\n",
    "                    ans %= MOD\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        # 122组合\n",
    "        for i in range(n):\n",
    "            x = nums[i]\n",
    "            if (target - x) % 2 == 0:\n",
    "                y = (target - x) // 2\n",
    "                if y != x:\n",
    "                    ans += cnt[x] * cnt[y] * (cnt[y] - 1) // 2\n",
    "                    ans %= MOD\n",
    "\n",
    "        # 111组合\n",
    "        if target % 3 == 0:\n",
    "            x = target // 3\n",
    "            ans += cnt[x] * (cnt[x] - 1) * (cnt[x] - 2) // 6\n",
    "            ans %= MOD\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        ans = 0\n",
    "        for i,a in enumerate(arr):\n",
    "            j,k = i + 1,n - 1\n",
    "            while j < k:\n",
    "                t = a + arr[j] + arr[k]\n",
    "                if t == target:\n",
    "                    if arr[j] == arr[k]:\n",
    "                        ans += comb((k - j + 1),2) % MOD\n",
    "                        ans %= MOD\n",
    "                        break\n",
    "                    else:\n",
    "                        l = j\n",
    "                        while l < k and arr[l] == arr[j]:\n",
    "                            l += 1\n",
    "                        r = k\n",
    "                        while j < r and arr[r] == arr[k]:\n",
    "                            r -= 1\n",
    "                        ans += (l - j)*(k - r) % MOD\n",
    "                        ans %= MOD\n",
    "                        j,k = l,r\n",
    "                elif t > target:\n",
    "                    k -= 1\n",
    "                else:\n",
    "                    j += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        count = collections.Counter(arr)\n",
    "        keys = sorted(count)\n",
    "        \n",
    "        ans = 0\n",
    "        \n",
    "        # Now, let's do a 3sum on \"keys\", for i <= j <= k.\n",
    "        # We will use count to add the correct contribution to ans.\n",
    "        for i, x in enumerate(keys):\n",
    "            T = target - x\n",
    "            j, k = i, len(keys) - 1\n",
    "            while j <= k:\n",
    "                y, z = keys[j], keys[k]\n",
    "                if y + z < T:\n",
    "                    j += 1\n",
    "                elif y + z > T:\n",
    "                    k -= 1\n",
    "                else: # x+y+z == T, now calculate the size of the contribution\n",
    "                    if i < j < k:\n",
    "                        ans += count[x] * count[y] * count[z]\n",
    "                    elif i == j < k:\n",
    "                        ans += count[x] * (count[x] - 1) / 2 * count[z]\n",
    "                    elif i < j == k:\n",
    "                        ans += count[x] * count[y] * (count[y] - 1) / 2\n",
    "                    else:\n",
    "                        ans += count[x] * (count[x] - 1) * (count[x] - 2) / 6\n",
    "\n",
    "                    j += 1\n",
    "                    k -= 1\n",
    "                    \n",
    "        return int(ans % MOD)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, A: List[int], target: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        count = collections.Counter(A)  # 频率\n",
    "        keys = sorted(count)  # key排序\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        # Now, let's do a 3sum on \"keys\", for i <= j <= k.\n",
    "        # We will use count to add the correct contribution to ans.\n",
    "        for i, x in enumerate(keys):\n",
    "            T = target - x\n",
    "            j, k = i, len(keys) - 1\n",
    "            while j <= k:\n",
    "                y, z = keys[j], keys[k]\n",
    "                if y + z < T:\n",
    "                    j += 1\n",
    "                elif y + z > T:\n",
    "                    k -= 1\n",
    "                else: # x+y+z == T, now calculate the size of the contribution\n",
    "                    if i < j < k:\n",
    "                        ans += count[x] * count[y] * count[z]\n",
    "                    elif i == j < k:\n",
    "                        ans += count[x] * (count[x] - 1) // 2 * count[z]\n",
    "                    elif i < j == k:\n",
    "                        ans += count[x] * count[y] * (count[y] - 1) // 2\n",
    "                    else:  # i == j == k\n",
    "                        ans += count[x] * (count[x] - 1) * (count[x] - 2) // 6\n",
    "\n",
    "                    j += 1\n",
    "                    k -= 1\n",
    "\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, nums: List[int], target: int) -> int:\n",
    "        ans = 0\n",
    "        MOD = 1000000007\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        for i in range(n-2):\n",
    "            l, r = i+1, n-1\n",
    "            while l < r:\n",
    "                # print(l, r)\n",
    "                t = nums[i]+nums[l]+nums[r]\n",
    "                if t < target:\n",
    "                    l += 1\n",
    "                elif t > target:\n",
    "                    r -= 1\n",
    "                elif nums[l] != nums[r]:\n",
    "                    ln, rn = 1, 1\n",
    "                    while l < r and nums[l] == nums[l+1]:\n",
    "                        l += 1\n",
    "                        ln += 1\n",
    "                    while l < r and nums[r] == nums[r-1]:\n",
    "                        r -= 1\n",
    "                        rn += 1\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "                    ans += ln*rn\n",
    "                    ans %= MOD\n",
    "                else:\n",
    "                    m = r-l+1\n",
    "                    ans += m*(m-1) // 2\n",
    "                    ans %= MOD\n",
    "                    l = r\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        if len(arr) < 3:\n",
    "            return 0\n",
    "        arr.sort()\n",
    "        res = 0\n",
    "        for i in range(len(arr) - 2):\n",
    "            left = i + 1\n",
    "            right = len(arr) - 1\n",
    "            while(left < right):\n",
    "                flag = 0\n",
    "                total = arr[i] + arr[left] + arr[right]\n",
    "                if total > target:\n",
    "                    right -= 1\n",
    "                elif total < target:\n",
    "                    left += 1\n",
    "                else:\n",
    "                    t1 = 1\n",
    "                    t2 = 1\n",
    "                    if arr[left] == arr[right]:\n",
    "                        res += (right - left + 1) * (right - left) // 2\n",
    "                        break\n",
    "                    while arr[left] == arr[left+1] and left + 1 <= right:\n",
    "                        t1 += 1\n",
    "                        left += 1\n",
    "                    while arr[right] == arr[right-1] and right - 1 >= left:\n",
    "                        t2 += 1\n",
    "                        right -= 1\n",
    "                    res += t1 * t2\n",
    "                    left += 1\n",
    "                    right -= 1\n",
    "        return res % (10 ** 9 +7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        res = 0\n",
    "        mod = 10**9 + 7\n",
    "        for i in range(len(arr)):\n",
    "            left = i + 1\n",
    "            right = len(arr) - 1\n",
    "            t = target - arr[i]\n",
    "            \n",
    "            while left < right:\n",
    "                if arr[left] + arr[right] < t:\n",
    "                    left += 1\n",
    "                elif arr[left] + arr[right] > t:\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    if arr[left] == arr[right]:\n",
    "                        count = right - left + 1\n",
    "                        res += count * (count-1) // 2\n",
    "                        break\n",
    "                    else:\n",
    "                        countleft = 1\n",
    "                        while left + 1 < right and arr[left] == arr[left+1]:\n",
    "                            countleft += 1\n",
    "                            left += 1\n",
    "                        countright = 1\n",
    "                        while left < right - 1 and arr[right] == arr[right-1]:\n",
    "                            countright += 1\n",
    "                            right -= 1\n",
    "\n",
    "                        res += countleft * countright\n",
    "                        left += 1\n",
    "                        right -= 1\n",
    "            \n",
    "        return res % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        res = 0\n",
    "        di = dict()\n",
    "        for num in arr:\n",
    "            di[num] = di.get(num, 0) + 1\n",
    "        for i in range(target + 1):\n",
    "            if i in di:\n",
    "                for j in range(i, target + 1):\n",
    "                    if j in di:\n",
    "                        k = target - i - j\n",
    "                        if k >= j and k in di:\n",
    "                            if i == j and j == k:   \n",
    "                                res += di[i] * (di[i] - 1) * (di[i] - 2) // 6\n",
    "                            elif i == j and j != k: \n",
    "                                res += di[i] * (di[i] - 1) // 2 * di[k]\n",
    "                            elif i != j and j == k:\n",
    "                                res += di[i] * di[j] * (di[j] - 1) // 2\n",
    "                            else:\n",
    "                                res += di[i] * di[j] * di[k]\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        mod = 1000000007\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            t2 = target - arr[i]\n",
    "            j = i + 1\n",
    "            k = n - 1\n",
    "            while j < k:\n",
    "                if arr[j] + arr[k] < t2:\n",
    "                    j += 1\n",
    "                elif arr[j] + arr[k] > t2:\n",
    "                    k -= 1\n",
    "                else: # equals t2\n",
    "                    if arr[j] != arr[k]:\n",
    "                        left = 1\n",
    "                        right = 1\n",
    "                        while j + 1 < k and arr[j] == arr[j + 1]:\n",
    "                            j += 1\n",
    "                            left += 1\n",
    "                        while j < k - 1 and arr[k - 1] == arr[k]:\n",
    "                            k -= 1\n",
    "                            right += 1\n",
    "                        ans += left * right\n",
    "                        ans %= mod\n",
    "                        j += 1\n",
    "                        k -= 1\n",
    "                        \n",
    "                    else: # [j~k] are all the same N!/((N-2))!(2)\n",
    "                        N = k - j + 1\n",
    "                        ans += (N * (N - 1) / 2)\n",
    "                        ans %= mod\n",
    "                        break\n",
    "                    \n",
    "        return int(ans)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        times = {}\n",
    "        arr.sort()\n",
    "        mod = 10**9 + 7\n",
    "        for i in arr:\n",
    "            if i not in times.keys():\n",
    "                times[i] = 1\n",
    "            else:\n",
    "                times[i]+=1\n",
    "        res = 0\n",
    "        for i in range(len(arr)):\n",
    "            times[arr[i]]-=1\n",
    "            l = i+1\n",
    "            r = len(arr)-1\n",
    "            while l<r:\n",
    "                if arr[i]+arr[l]+arr[r]==target:\n",
    "                    if arr[l]!=arr[r]:\n",
    "                        res+=times[arr[l]]*times[arr[r]]\n",
    "                        l+=times[arr[l]]\n",
    "                        r-=times[arr[r]]\n",
    "                        res=res%mod\n",
    "                    \n",
    "                    else:\n",
    "                        res+=(times[arr[l]]-1)*times[arr[l]]//2\n",
    "                        res = res%mod\n",
    "                        break\n",
    "                    \n",
    "                elif arr[i]+arr[l]+arr[r]>target:\n",
    "                    r-=1\n",
    "                elif arr[i]+arr[l]+arr[r]<target:\n",
    "                    l+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        a = {}\n",
    "        for ar in arr:\n",
    "            if ar in a:\n",
    "                a[ar] += 1\n",
    "            else:\n",
    "                a[ar] = 1\n",
    "        nums = list(a.keys())\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        if target % 3 == 0:\n",
    "            k = target//3\n",
    "            if k in a:\n",
    "                if a[k] >=3:\n",
    "                    res = (res + (a[k]-2)*(a[k]-1)*a[k]//6) % MOD \n",
    "\n",
    "        for num in nums:\n",
    "            if a[num] >= 2:\n",
    "                k = target - num*2\n",
    "                if k in nums and k != num:\n",
    "                    res = (res + (a[num]-1)*a[num]//2*a[k]) % MOD\n",
    "\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                k = target - nums[i] - nums[j]\n",
    "                if k > nums[j] and k in nums:\n",
    "                    res = (res + a[nums[i]]*a[nums[j]]*a[k]) % MOD\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        #时间复杂度O(n^2)\n",
    "        arr.sort()\n",
    "        n=len(arr)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            x=defaultdict(int)\n",
    "            cur=target-arr[i]\n",
    "            #两数之和操作\n",
    "            for j in range(i+1,n):\n",
    "                ans+=x[arr[j]]\n",
    "                x[cur-arr[j]]+=1\n",
    "        return ans%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def threeSumMulti(self, A: List[int], target: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        count = collections.Counter(A)\n",
    "        keys = sorted(count)\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        # Now, let's do a 3sum on \"keys\", for i <= j <= k.\n",
    "        # We will use count to add the correct contribution to ans.\n",
    "        for i, x in enumerate(keys):\n",
    "            T = target - x\n",
    "            j, k = i, len(keys) - 1\n",
    "            while j <= k:\n",
    "                y, z = keys[j], keys[k]\n",
    "                if y + z < T:\n",
    "                    j += 1\n",
    "                elif y + z > T:\n",
    "                    k -= 1\n",
    "                else: # x+y+z == T, now calculate the size of the contribution\n",
    "                    if i < j < k:\n",
    "                        ans += count[x] * count[y] * count[z]\n",
    "                    elif i == j < k:\n",
    "                        ans += count[x] * (count[x] - 1) / 2 * count[z]\n",
    "                    elif i < j == k:\n",
    "                        ans += count[x] * count[y] * (count[y] - 1) / 2\n",
    "                    else:  # i == j == k\n",
    "                        ans += count[x] * (count[x] - 1) * (count[x] - 2) / 6\n",
    "\n",
    "                    j += 1\n",
    "                    k -= 1\n",
    "\n",
    "        return int(ans % MOD)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        # 三数之和 = 枚举一数+二数之和\n",
    "        arr.sort()\n",
    "        mod = 10**9+7\n",
    "        ans = 0\n",
    "        for i,x in enumerate(arr):\n",
    "            T = target - x\n",
    "            # 双指针两数之和\n",
    "            j = i+1\n",
    "            k = len(arr)-1\n",
    "            while j < k:\n",
    "                if arr[j] + arr[k] > T:\n",
    "                    k -= 1\n",
    "                elif arr[j] + arr[k] < T:\n",
    "                    j += 1\n",
    "                # arr[j] + arr[k] = T 可分为两种情况 arr[j] != arr[k],arr[j] = arr[k]\n",
    "                elif arr[j] != arr[k]:\n",
    "                    # 统计左边相同值的个数\n",
    "                    c_l = 1\n",
    "                    while j + 1 < k and arr[j] == arr[j+1]:\n",
    "                        c_l += 1\n",
    "                        j += 1\n",
    "                    # 统计右边相同值的个数\n",
    "                    c_r = 1\n",
    "                    while k - 1 > j and arr[k] == arr[k-1]:\n",
    "                        c_r += 1\n",
    "                        k -= 1\n",
    "                    ans += c_l*c_r\n",
    "                    k -= 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    ans += (k-j+1)*(k-j)//2\n",
    "                    break\n",
    "        return ans%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        cnt = collections.Counter(arr)\n",
    "        nums = sorted(cnt)\n",
    "        ans = 0\n",
    "        for k, kv in enumerate(nums):\n",
    "            l, r = 0, k\n",
    "            while l <= r:\n",
    "                if nums[l] + nums[r] + kv < target:\n",
    "                    l += 1\n",
    "                elif nums[l] + nums[r] + kv > target:\n",
    "                    r -= 1\n",
    "                else:\n",
    "                    if l < r < k:\n",
    "                        ans += cnt[nums[l]] * cnt[nums[r]] * cnt[kv]\n",
    "                    elif l == r < k:\n",
    "                        ans += cnt[nums[l]] * (cnt[nums[l]] - 1) / 2 * cnt[kv]\n",
    "                    elif l < r == k:\n",
    "                        ans += cnt[kv] * (cnt[kv] - 1) / 2 * cnt[nums[l]]\n",
    "                    else:\n",
    "                        ans += cnt[kv] * (cnt[kv] - 1) * (cnt[kv] - 2) / 6\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "        return int(ans) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        # 如果直接枚举 i,j,k,时间复杂度为O(n**3)\n",
    "        # 那么需要优化\n",
    "        # 然后有一个O(n)的双指针方法求 arr[j] + arr[k] == target的方法\n",
    "        # 融合这两个方法可以得到一个时间复杂度为O(n**2)的方法\n",
    "        arr.sort()\n",
    "        res = 0\n",
    "        for i,x in enumerate(arr):\n",
    "            T = target - x\n",
    "            j = i+1\n",
    "            k = len(arr)-1\n",
    "            # 双指针模板\n",
    "            while j < k:\n",
    "                if arr[j] + arr[k] > T:\n",
    "                    k -= 1\n",
    "                elif arr[j] + arr[k] < T:\n",
    "                    j += 1\n",
    "                # arr[j] + arr[k] = T 拆分为两种情况\n",
    "                elif arr[j] != arr[k]:\n",
    "                    # 统计左边相同的个数\n",
    "                    left = 1\n",
    "                    while j+1 < k and arr[j] == arr[j+1]:\n",
    "                        j += 1\n",
    "                        left += 1\n",
    "                    # 统计右边相同的个数\n",
    "                    right = 1\n",
    "                    while k-1 > j and arr[k] == arr[k-1]:\n",
    "                        k -= 1\n",
    "                        right += 1\n",
    "                    # 统计一下结果\n",
    "                    res += left*right\n",
    "                    j += 1\n",
    "                    k -= 1\n",
    "                else:\n",
    "                    res += (k-j+1)*(k-j)//2\n",
    "                    break\n",
    "        return res%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        count = 0\n",
    "        n = len(arr)\n",
    "        arr.sort()\n",
    "        mod = 10**9 + 7\n",
    "\n",
    "        for i in range(n):\n",
    "            t = target - arr[i]\n",
    "            j, k = i + 1, n - 1\n",
    "\n",
    "            while j < k:\n",
    "                if arr[j] + arr[k] < t:\n",
    "                    j += 1\n",
    "                elif arr[j] + arr[k] > t:\n",
    "                    k -= 1\n",
    "                elif arr[j] != arr[k]:\n",
    "                    left = right = 1\n",
    "                    while j + 1 < k and arr[j] == arr[j + 1]:\n",
    "                        left += 1\n",
    "                        j += 1\n",
    "                    while k - 1 > j and arr[k] == arr[k - 1]:\n",
    "                        right += 1\n",
    "                        k -= 1\n",
    "                    count += left * right\n",
    "                    count %= mod\n",
    "                    j += 1\n",
    "                    k -= 1\n",
    "                else:\n",
    "                    count += (k - j + 1) * (k - j) // 2\n",
    "                    count %= mod\n",
    "                    break\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        cnt = collections.Counter(arr)  # 把相同的数字压缩\n",
    "        nums = sorted(cnt)  # 不同的数字列表\n",
    "        ans = 0\n",
    "        for k, kv in enumerate(nums): # 枚举第3个数\n",
    "            l, r = 0, k  # 由于数字可以相同，所以可以重合\n",
    "            while l <= r:  # 由于数字可以相同，所以可以重合\n",
    "                if nums[l] + nums[r] + kv < target:\n",
    "                    l += 1\n",
    "                elif nums[l] + nums[r] + kv > target:\n",
    "                    r -= 1\n",
    "                else: # 分类讨论，相等时的情况\n",
    "                    if l < r < k: # 三个都不同\n",
    "                        ans += cnt[nums[l]] * cnt[nums[r]] * cnt[kv]\n",
    "                    elif l == r < k: # 有两个相同Cn2\n",
    "                        ans += cnt[nums[l]] * (cnt[nums[l]] - 1) / 2 * cnt[kv]\n",
    "                    elif l < r == k: # 有两个相同Cn2\n",
    "                        ans += cnt[kv] * (cnt[kv] - 1) / 2 * cnt[nums[l]]\n",
    "                    else: # 都相同Cn3\n",
    "                        ans += cnt[kv] * (cnt[kv] - 1) * (cnt[kv] - 2) / 6\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "        return int(ans) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        dp = [[0, 0, 0, 0] for _ in range(target + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in arr:\n",
    "            for j in range(target, i - 1, -1):\n",
    "                for k in range(3, 0, -1):\n",
    "                    dp[j][k] += dp[j - i][k - 1]\n",
    "        return dp[-1][-1] % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        cnt = collections.Counter(arr)  # 把相同的数字压缩\n",
    "        nums = sorted(cnt)  # 不同的数字列表\n",
    "        ans = 0\n",
    "        for k, kv in enumerate(nums): # 枚举第3个数\n",
    "            l, r = 0, k  # 由于数字可以相同，所以可以重合\n",
    "            while l <= r:  # 由于数字可以相同，所以可以重合\n",
    "                if nums[l] + nums[r] + kv < target:\n",
    "                    l += 1\n",
    "                elif nums[l] + nums[r] + kv > target:\n",
    "                    r -= 1\n",
    "                else: # 分类讨论，相等时的情况\n",
    "                    if l != r != k: # 三个都不同\n",
    "                        ans += cnt[nums[l]] * cnt[nums[r]] * cnt[kv]\n",
    "                    elif l == r != k: # 有两个相同Cn2\n",
    "                        ans += cnt[nums[l]] * (cnt[nums[l]] - 1) / 2 * cnt[kv]\n",
    "                    elif l != r == k: # 有两个相同Cn2\n",
    "                        ans += cnt[kv] * (cnt[kv] - 1) / 2 * cnt[nums[l]]\n",
    "                    else: # 都相同Cn3\n",
    "                        ans += cnt[kv] * (cnt[kv] - 1) * (cnt[kv] - 2) / 6\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "        return int(ans) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        ans = 0\n",
    "        MOD = 10**9 + 7\n",
    "        arr.sort()\n",
    "        for k in range(2, n):\n",
    "            l, r = 0, k - 1\n",
    "            while l < r:\n",
    "                if arr[l] + arr[r] + arr[k] == target:\n",
    "                    i, j = l, r\n",
    "                    if arr[l] == arr[r]:  # 如果两个指向相等元素，则为Cn2\n",
    "                        ans = (ans + (r - l) * (r - l + 1) // 2) % MOD\n",
    "                        break\n",
    "                    while arr[i] == arr[l]: i += 1\n",
    "                    while arr[j] == arr[r]: j -= 1\n",
    "                    ans = (ans + (i - l) * (r - j)) % MOD  # 两个元素不同，则为x*y\n",
    "                    l, r = i, j\n",
    "                elif arr[l] + arr[r] + arr[k] < target:\n",
    "                    l += 1\n",
    "                else:\n",
    "                    r -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def threeSumMulti(self, A, target):\n",
    "        MOD = 10**9 + 7\n",
    "        count = collections.Counter(A)\n",
    "        keys = sorted(count)\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        # Now, let's do a 3sum on \"keys\", for i <= j <= k.\n",
    "        # We will use count to add the correct contribution to ans.\n",
    "        for i, x in enumerate(keys):\n",
    "            T = target - x\n",
    "            j, k = i, len(keys) - 1\n",
    "            while j <= k:\n",
    "                y, z = keys[j], keys[k]\n",
    "                if y + z < T:\n",
    "                    j += 1\n",
    "                elif y + z > T:\n",
    "                    k -= 1\n",
    "                else: # x+y+z == T, now calculate the size of the contribution\n",
    "                    if i < j < k:\n",
    "                        ans += count[x] * count[y] * count[z]\n",
    "                    elif i == j < k:\n",
    "                        ans += count[x] * (count[x] - 1) / 2 * count[z]\n",
    "                    elif i < j == k:\n",
    "                        ans += count[x] * count[y] * (count[y] - 1) / 2\n",
    "                    else:  # i == j == k\n",
    "                        ans += count[x] * (count[x] - 1) * (count[x] - 2) / 6\n",
    "\n",
    "                    j += 1\n",
    "                    k -= 1\n",
    "\n",
    "        return int(ans % MOD)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        count = collections.Counter(arr)\n",
    "        keys = sorted(count)\n",
    "        \n",
    "        ans = 0\n",
    "        \n",
    "        # Now, let's do a 3sum on \"keys\", for i <= j <= k.\n",
    "        # We will use count to add the correct contribution to ans.\n",
    "        for i, x in enumerate(keys):\n",
    "            T = target - x\n",
    "            j, k = i, len(keys) - 1\n",
    "            while j <= k:\n",
    "                y, z = keys[j], keys[k]\n",
    "                if y + z < T:\n",
    "                    j += 1\n",
    "                elif y + z > T:\n",
    "                    k -= 1\n",
    "                else: # x+y+z == T, now calculate the size of the contribution\n",
    "                    if i < j < k:\n",
    "                        ans += count[x] * count[y] * count[z]\n",
    "                    elif i == j < k:\n",
    "                        ans += count[x] * (count[x] - 1) / 2 * count[z]\n",
    "                    elif i < j == k:\n",
    "                        ans += count[x] * count[y] * (count[y] - 1) / 2\n",
    "                    else:\n",
    "                        ans += count[x] * (count[x] - 1) * (count[x] - 2) / 6\n",
    "\n",
    "                    j += 1\n",
    "                    k -= 1\n",
    "                    \n",
    "        return int(ans % MOD)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        count = [0] * 101\n",
    "        unique_nums = 0\n",
    "        for num in arr:\n",
    "            count[num] += 1\n",
    "            if count[num] == 1:\n",
    "                unique_nums += 1\n",
    "        \n",
    "        keys = []\n",
    "        for idx, num in enumerate(count):\n",
    "            if num > 0:\n",
    "                keys.append(idx)\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(len(keys)):\n",
    "            a = keys[i]\n",
    "            T = target - a\n",
    "            left, right = i, len(keys) - 1\n",
    "            \n",
    "            while left <= right:\n",
    "                b, c = keys[left], keys[right]\n",
    "                \n",
    "                if b + c < T:\n",
    "                    left += 1\n",
    "                elif b + c > T:\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    if i < left < right:\n",
    "                        res += count[a] * count[b] * count[c]\n",
    "                    elif i == left < right:\n",
    "                        res += count[a] * (count[a] - 1) // 2 * count[c]\n",
    "                    elif i < left == right:\n",
    "                        res += count[a] * count[b] * (count[b] - 1) // 2\n",
    "                    else:\n",
    "                        res += count[a] * (count[a] - 1) * (count[a] - 2) // 6\n",
    "                    \n",
    "                    res %= MOD\n",
    "                    left += 1\n",
    "                    right -= 1\n",
    "        \n",
    "        return res % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def threeSumMulti(self, A, target):\n",
    "        MOD = 10**9+7\n",
    "        ans = 0\n",
    "        A.sort()\n",
    "\n",
    "        for i,x in enumerate(A):\n",
    "            j,k = i+1, len(A) -1\n",
    "            T = target - A[i]\n",
    "\n",
    "            while j < k:\n",
    "                if A[j]+A[k] < T:\n",
    "                    j += 1\n",
    "                elif A[j] + A[k] > T:\n",
    "                    k -= 1\n",
    "                else:\n",
    "                    if A[j] == A[k]:\n",
    "                        ans += (k-j+1)*(k-j)/2\n",
    "                        ans %= MOD\n",
    "                        break\n",
    "                    left = right = 1\n",
    "                    while j+1 < k and A[j] == A[j+1]:\n",
    "                        left += 1\n",
    "                        j += 1\n",
    "                        # print(i,j,k)\n",
    "                    while j < k-1 and A[k-1] == A[k]:\n",
    "                        right += 1\n",
    "                        k -=1\n",
    "\n",
    "                    # print(left*right)\n",
    "                    ans += left*right\n",
    "                    ans %= MOD\n",
    "                    j+=1\n",
    "                    k-=1\n",
    "        return int(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "三指针\n",
    "两数之和，双指针可行\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def threeSumMulti(self, A: List[int], target: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        ans = 0\n",
    "        A.sort()  # 排序\n",
    "\n",
    "        for i, x in enumerate(A):\n",
    "            # We'll try to find the number of i < j < k\n",
    "            # with A[j] + A[k] == T, where T = target - A[i].\n",
    "\n",
    "            # The below is a \"two sum with multiplicity\".\n",
    "            T = target - A[i]\n",
    "            j, k = i+1, len(A) - 1\n",
    "\n",
    "            while j < k:\n",
    "                # These steps proceed as in a typical two-sum.\n",
    "                if A[j] + A[k] < T:\n",
    "                    j += 1\n",
    "                elif A[j] + A[k] > T:\n",
    "                    k -= 1\n",
    "                # These steps differ:\n",
    "                elif A[j] != A[k]: # We have A[j] + A[k] == T.\n",
    "                    # Let's count \"left\": the number of A[j] == A[j+1] == A[j+2] == ...\n",
    "                    # And similarly for \"right\".\n",
    "                    left = right = 1\n",
    "                    while j + 1 < k and A[j] == A[j+1]:\n",
    "                        left += 1\n",
    "                        j += 1\n",
    "                    while k - 1 > j and A[k] == A[k-1]:\n",
    "                        right += 1\n",
    "                        k -= 1\n",
    "\n",
    "                    # We contributed left * right many pairs.\n",
    "                    ans += left * right\n",
    "                    ans %= MOD\n",
    "                    j += 1\n",
    "                    k -= 1\n",
    "\n",
    "                else:\n",
    "                    # M = k - j + 1\n",
    "                    # We contributed M * (M-1) / 2 pairs.\n",
    "                    ans += (k-j+1) * (k-j) // 2\n",
    "                    ans %= MOD\n",
    "                    break\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr, target):\n",
    "        arr.sort()\n",
    "        cnt = 0\n",
    "        MOD = 10**9 + 7\n",
    "\n",
    "        for i in range(0, len(arr)):\n",
    "            left_p = i + 1\n",
    "            right_p = len(arr) - 1\n",
    "\n",
    "            while right_p > left_p:\n",
    "                if arr[i] + arr[left_p] + arr[right_p] == target: \n",
    "                    if arr[left_p] == arr[right_p]:\n",
    "                        cnt += (right_p - left_p) * (right_p - left_p + 1) / 2\n",
    "                        break\n",
    "                    else:\n",
    "                        l_c = 1\n",
    "                        r_c = 1\n",
    "                        while arr[left_p + 1] == arr[left_p]:\n",
    "                            l_c += 1\n",
    "                            left_p += 1\n",
    "                        \n",
    "                        while arr[right_p - 1] == arr[right_p]:\n",
    "                            r_c += 1\n",
    "                            right_p -= 1 \n",
    "                        \n",
    "                        cnt += l_c * r_c\n",
    "                        left_p += 1\n",
    "                        right_p -= 1\n",
    "                elif arr[i] + arr[left_p] + arr[right_p] > target:\n",
    "                    right_p -= 1\n",
    "                else:\n",
    "                    left_p += 1\n",
    "        \n",
    "        res = int(cnt) % MOD\n",
    "        return res\n",
    "            \n",
    "if __name__ == \"__main__\":\n",
    "    arr = [1,1,2,2,3,3,4,4,5,5]\n",
    "    target = 8\n",
    "    print(Solution().threeSumMulti(arr, target))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        ans = 0\n",
    "        dic = collections.Counter(arr)\n",
    "        sortedDic = sorted(dic.items())\n",
    "        n = len(sortedDic)\n",
    "\n",
    "        for i, (num, cnt) in enumerate(sortedDic):\n",
    "            twoSum = target-num\n",
    "            j, k = i+1, n-1\n",
    "            if sortedDic[i][0] * 3 == target and sortedDic[i][1]>=3:\n",
    "                ans += sortedDic[i][1] * (sortedDic[i][1]-1)* (sortedDic[i][1]-2)/6\n",
    "                ans %= MOD\n",
    "\n",
    "            while j<=k:\n",
    "                if sortedDic[j][0] + sortedDic[k][0] < twoSum:\n",
    "                    j += 1\n",
    "                elif sortedDic[j][0] + sortedDic[k][0] > twoSum:\n",
    "                    k -= 1\n",
    "                elif j<k:\n",
    "                    ans += sortedDic[j][1] * sortedDic[k][1]*cnt\n",
    "                    ans %= MOD\n",
    "                    j += 1\n",
    "                    k -= 1\n",
    "                else:\n",
    "                    ans += cnt*sortedDic[j][1] *(sortedDic[j][1]-1) / 2\n",
    "                    ans %= MOD\n",
    "                    break\n",
    "\n",
    "            if cnt >= 2:\n",
    "                j = i+1\n",
    "                while j<n:\n",
    "                    total = 2*num + sortedDic[j][0]\n",
    "                    if total > target:\n",
    "                        break\n",
    "                    elif total <target:\n",
    "                        j += 1\n",
    "                    else:\n",
    "                        ans += sortedDic[j][1] *cnt * (cnt-1) /2\n",
    "                        ans %= MOD\n",
    "                        break\n",
    "            \n",
    "        return int(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        cnt = Counter(arr)\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        mod = 10**9+7       \n",
    "        ans = 0\n",
    "        for i in range(n-2):\n",
    "            cnt[arr[i]] -= 1\n",
    "            g = cnt.copy()\n",
    "            for j in range(i+1,n-1):\n",
    "                # print(g,cnt)\n",
    "                g[arr[j]] -= 1\n",
    "                t = target - arr[i] - arr[j]\n",
    "                if t < arr[0]:\n",
    "                    break\n",
    "                ans += g[t]%mod\n",
    "        return ans%mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        n=len(arr)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            x=defaultdict(int)\n",
    "            cur=target-arr[i]\n",
    "            #两数之和操作\n",
    "            for j in range(i+1,n):\n",
    "                ans+=x[arr[j]]\n",
    "                x[cur-arr[j]]+=1\n",
    "        return ans%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        n=len(arr)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            x=defaultdict(int)\n",
    "            cur=target-arr[i]\n",
    "            #两数之和操作\n",
    "            for j in range(i+1,n):\n",
    "                ans+=x[arr[j]]\n",
    "                x[cur-arr[j]]+=1\n",
    "        return ans%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        ans, count, nums = 0, {}, []\n",
    "        for a in arr:\n",
    "            if a not in count:\n",
    "                count[a] = 0\n",
    "                nums.append(a)\n",
    "            count[a] += 1\n",
    "        \n",
    "        nums = sorted(nums)\n",
    "        n = len(nums)\n",
    "\n",
    "        for i in range(0, n - 2):\n",
    "            if nums[i] > target:\n",
    "                break\n",
    "            for j in range(i+1, n - 1):\n",
    "                if nums[i] + nums[j] > target:\n",
    "                    break\n",
    "                for k in range(j+1, n):\n",
    "                    if nums[i] + nums[j] + nums[k] == target:\n",
    "                        ans += count[nums[i]] * count[nums[j]] * count[nums[k]]\n",
    "                        ans %= mod\n",
    "                        break\n",
    "\n",
    "        for i in range(0, n - 1):\n",
    "            if nums[i] > target:\n",
    "                break\n",
    "            if count[nums[i]] > 1:\n",
    "                if nums[i] * 2 > target:\n",
    "                    break\n",
    "                for j in range(i+1, n):\n",
    "                    if nums[i] * 2 + nums[j] == target:\n",
    "                        x = math.comb(count[nums[i]], 2)\n",
    "                        ans += x * count[nums[j]]\n",
    "                        ans %= mod\n",
    "            for j in range(i+1, n):\n",
    "                if count[nums[j]] > 1 and nums[i] + nums[j] * 2 == target:\n",
    "                    x = math.comb(count[nums[j]], 2)\n",
    "                    ans += count[nums[i]] * x\n",
    "                    ans %= mod\n",
    "        \n",
    "        for i in range(0, n):\n",
    "            if count[nums[i]] > 2 and nums[i] * 3 == target:\n",
    "                ans += math.comb(count[nums[i]], 3)\n",
    "                ans %= mod\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def threeSumMulti(self, A, target):\n",
    "        MOD = 10**9 + 7\n",
    "        ans = 0\n",
    "        A.sort()\n",
    "\n",
    "        for i, x in enumerate(A):\n",
    "            # We'll try to find the number of i < j < k\n",
    "            # with A[j] + A[k] == T, where T = target - A[i].\n",
    "\n",
    "            # The below is a \"two sum with multiplicity\".\n",
    "            T = target - A[i]\n",
    "            j, k = i+1, len(A) - 1\n",
    "\n",
    "            while j < k:\n",
    "                # These steps proceed as in a typical two-sum.\n",
    "                if A[j] + A[k] < T:\n",
    "                    j += 1\n",
    "                elif A[j] + A[k] > T:\n",
    "                    k -= 1\n",
    "                # These steps differ:\n",
    "                elif A[j] != A[k]: # We have A[j] + A[k] == T.\n",
    "                    # Let's count \"left\": the number of A[j] == A[j+1] == A[j+2] == ...\n",
    "                    # And similarly for \"right\".\n",
    "                    left = right = 1\n",
    "                    while j + 1 < k and A[j] == A[j+1]:\n",
    "                        left += 1\n",
    "                        j += 1\n",
    "                    while k - 1 > j and A[k] == A[k-1]:\n",
    "                        right += 1\n",
    "                        k -= 1\n",
    "\n",
    "                    # We contributed left * right many pairs.\n",
    "                    ans += left * right\n",
    "                    ans %= MOD\n",
    "                    j += 1\n",
    "                    k -= 1\n",
    "\n",
    "                else:\n",
    "                    # M = k - j + 1\n",
    "                    # We contributed M * (M-1) / 2 pairs.\n",
    "                    ans += (k-j+1) * (k-j) / 2\n",
    "                    ans %= MOD\n",
    "                    break\n",
    "\n",
    "        return int(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        cnt = Counter(arr)\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        mod = 10**9+7\n",
    "        # visit = set()\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n-2):\n",
    "            cnt[arr[i]] -= 1\n",
    "            g = cnt.copy()\n",
    "            for j in range(i+1,n-1):\n",
    "                # print(g,cnt)\n",
    "                g[arr[j]] -= 1\n",
    "                t = target - arr[i] - arr[j]\n",
    "                if t < 0:\n",
    "                    break\n",
    "                # com = tuple(sorted([arr[i],arr[j],t]))\n",
    "                # print(arr[i],arr[j],t,cnt[t])\n",
    "                ans += g[t]%mod\n",
    "                # if g[t]:\n",
    "                #     ans += g[t]\n",
    "                #     ans %= mod\n",
    "                    # visit.add(com)\n",
    "                    # print(arr[i],arr[j],t,cnt[t])\n",
    "                # if t != arr[i] and t != arr[j]:\n",
    "                #     ans += cnt[t]\n",
    "                # elif t == arr[i] and t == arr[j]:\n",
    "                #     ans += cnt[t] - 2\n",
    "                # else:\n",
    "                #     ans += cnt[t] - 1\n",
    "                # ans %= mod\n",
    "        return ans%mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, A: List[int], target: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        n = len(A)\n",
    "        A.sort()\n",
    "        first_idx, last_idx = {}, {}\n",
    "        for i, num in enumerate(A):\n",
    "            if num not in first_idx:\n",
    "                first_idx[num] = i\n",
    "            last_idx[num] = i  # 记录排序后，0-9最后出现的位置\n",
    "        ans = 0\n",
    "\n",
    "        for first in range(n - 2):  # 枚举第一个元素\n",
    "            second, third = first + 1, n - 1\n",
    "            two_target = target - A[first]\n",
    "            while second < third:\n",
    "                s = A[second] + A[third]\n",
    "                if s > two_target:  # 当前数值太大\n",
    "                    third -= 1\n",
    "                elif s < two_target:  # 当前数值太小\n",
    "                    second += 1\n",
    "                else:  # 遇到一个组合能够满足了\n",
    "                    if A[second] == A[third]:\n",
    "                        num_second = last_idx[A[third]] - max(second, first) + 1\n",
    "                        ans += num_second * (num_second-1) // 2 # 这个组合的数量\n",
    "                        break                                   # 直接枚举第二个first\n",
    "                    else:\n",
    "                        num_second = last_idx[A[second]] - max(second, first) + 1\n",
    "                        num_third = third - first_idx[A[third]] + 1\n",
    "                        ans = ans + num_second * num_third  # 这个组合的数量\n",
    "                        third = first_idx[A[third]] - 1     # 重新赋值\n",
    "                        second = last_idx[A[second]] + 1            \n",
    "        ans %= MOD\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        mp = defaultdict(int)\n",
    "        ans = 0\n",
    "        n = len(arr)\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(n):\n",
    "            mp.clear()\n",
    "            t = target - arr [i]\n",
    "            for j in range(i + 1, n):\n",
    "                if t - arr[j] in mp:\n",
    "                    ans = (ans + mp[t - arr[j]]) % mod\n",
    "                mp[arr[j]] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        ans = 0\n",
    "        x = Counter(arr)\n",
    "        arr = sorted(list(set(arr)))\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            for j in range(i + 1, len(arr)):\n",
    "                if arr[i] + arr[j] > target:\n",
    "                    break\n",
    "                k = target - arr[i] - arr[j]\n",
    "                if k > arr[j]:\n",
    "                    ans += x[arr[i]] * x[arr[j]] * x[k]\n",
    "\n",
    "        for i in x:\n",
    "            if x[i] == 1:\n",
    "                continue\n",
    "            j = target - 2 * i\n",
    "            if i != j and j in x:\n",
    "                ans += ((x[i] * (x[i] - 1)) // 2) * x[j]\n",
    "        \n",
    "        s = target // 3\n",
    "        if s in x and x[s] >= 3 and target % 3 == 0:\n",
    "            ans += (x[s] * (x[s] - 1) * (x[s] - 2)) // 6\n",
    "        \n",
    "        return ans % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        res = 0\n",
    "        n = len(arr)\n",
    "        for i in range(n):\n",
    "            if arr[i] > target:\n",
    "                continue\n",
    "            tmp = target - arr[i]\n",
    "            d = {}\n",
    "            for j in range(i+1,n):\n",
    "                if arr[j] > tmp:\n",
    "                    continue\n",
    "                else:\n",
    "                    if (tmp - arr[j]) in d:\n",
    "                        res = (res+d[tmp-arr[j]])%1000000007\n",
    "                    if arr[j] in d:\n",
    "                        d[arr[j]] += 1\n",
    "                    else:\n",
    "                        d[arr[j]] = 1\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        mp = {}\n",
    "        for x in arr:\n",
    "            mp[x] = mp.get(x, 0) + 1\n",
    "        # print(mp)\n",
    "        ans, n = 0, len(mp)\n",
    "        nums = [0] * n\n",
    "        i = 0\n",
    "        for x in mp:\n",
    "            nums[i] = x\n",
    "            i+=1\n",
    "        # print('nums : ',nums)\n",
    "\n",
    "        for i in range(n):\n",
    "            l, r = i, n-1\n",
    "            while l<=r:\n",
    "                tmpsum = nums[i] + nums[l] + nums[r]\n",
    "                # print('i:{}, l:{}, r:{}, ans:{}, sum:{}'.format(i, l, r, ans, tmpsum))\n",
    "                if tmpsum > target:\n",
    "                    r-=1\n",
    "                elif tmpsum < target:\n",
    "                    l+=1\n",
    "                else:\n",
    "                    cnt1, cnt2 = 0, 0\n",
    "                    def calcnt(n1, n2)->int:\n",
    "                        cnt1 = mp[nums[n1]]\n",
    "                        cnt2 = mp[nums[n2]]\n",
    "                        # print('cal before [{}, {}]'.format(cnt1,cnt2))\n",
    "                        if cnt1 == 1:\n",
    "                            cnt1 = 0\n",
    "                        elif cnt1 == 2:\n",
    "                            cnt1 = 1\n",
    "                        else:\n",
    "                            cnt1 = comb(cnt1, 2)\n",
    "                        # print('calcnt({}, {}) -> {}'.format(n1, n2, cnt1*cnt2))\n",
    "                        return cnt1 * cnt2\n",
    "                    if (i == l and l != r):\n",
    "                        ans += calcnt(i, r)\n",
    "                    elif (i!=l and l==r):\n",
    "                        ans += calcnt(r, i)\n",
    "                    elif i!=l and l!=r:\n",
    "                        ans += mp[nums[i]] * mp[nums[l]] * mp[nums[r]]\n",
    "                    else: # 三者相等\n",
    "                        # print('i : {}, l : {}, r : {}'.format(i,l,r))\n",
    "                        cnt1 = mp[nums[i]]\n",
    "                        if cnt1 < 3:\n",
    "                            cnt1 = 0\n",
    "                        elif cnt1 == 3:\n",
    "                            cnt1 = 1\n",
    "                        else:\n",
    "                            cnt1 = comb(cnt1, 3)\n",
    "                        ans += cnt1\n",
    "                    l+=1\n",
    "\n",
    "\n",
    "        return ans % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def modAdd(a, b, modNum):\n",
    "    return ((a % modNum) + (b % modNum)) % modNum\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        modNum = 10**9 + 7\n",
    "        c = Counter(arr)\n",
    "        numLst = sorted(list(c.keys()))\n",
    "        rtnAns = 0\n",
    "        for i in range(len(numLst)):  # 外层指针\n",
    "            innerTarget = target - numLst[i]\n",
    "            j, k = i, len(numLst) - 1\n",
    "            while j <= k:\n",
    "                innerSum = numLst[j] + numLst[k]\n",
    "                match (innerSum>innerTarget) - (innerTarget>innerSum):\n",
    "                    case -1: # <\n",
    "                        j += 1\n",
    "                    case 0:\n",
    "                        if i == j and j == k:\n",
    "                            iCount = c[numLst[i]]\n",
    "                            if iCount >= 3:\n",
    "                                rtnAns = modAdd(rtnAns, (iCount * (iCount - 1) * (iCount -2)) // (3 * 2 * 1), modNum)\n",
    "                                # rtnAns += (iCount * (iCount - 1) * (iCount -2)) // (3 * 2 * 1)\n",
    "                        elif j == k:\n",
    "                            iCount = c[numLst[i]]\n",
    "                            jCount = c[numLst[j]]\n",
    "                            if jCount >= 2:\n",
    "                                rtnAns = modAdd(rtnAns, iCount * ((jCount * (jCount - 1)) // (2 * 1)), modNum)\n",
    "                                # rtnAns += iCount * ((jCount * (jCount - 1)) // (2 * 1))\n",
    "                        elif i == j:\n",
    "                            iCount = c[numLst[i]]\n",
    "                            kCount = c[numLst[k]]\n",
    "                            if iCount >= 2:\n",
    "                                rtnAns = modAdd(rtnAns, ((iCount * (iCount - 1)) // (2 * 1)) * kCount, modNum)\n",
    "                                # rtnAns += ((iCount * (iCount - 1)) // (2 * 1)) * kCount\n",
    "                        elif i == k:\n",
    "                            iCount = c[numLst[i]]\n",
    "                            jCount = c[numLst[j]]\n",
    "                            if iCount >= 2:\n",
    "                                rtnAns = modAdd(rtnAns, ((iCount * (iCount - 1)) // (2 * 1)) * jCount, modNum)\n",
    "                                # rtnAns += ((iCount * (iCount - 1)) // (2 * 1)) * jCount\n",
    "                        else:\n",
    "                            rtnAns = modAdd(rtnAns, c[numLst[i]] * c[numLst[j]] * c[numLst[k]], modNum)\n",
    "                            # rtnAns += c[numLst[i]] * c[numLst[j]] * c[numLst[k]]\n",
    "                        # break 这里不能 break 否则便会找不到所有的可能\n",
    "                        j += 1\n",
    "                        k -= 1\n",
    "                    case 1: # >\n",
    "                        k -= 1\n",
    "        return rtnAns"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        count = [0] * 101\n",
    "        unique_nums = 0\n",
    "        for num in arr:\n",
    "            count[num] += 1\n",
    "            if count[num] == 1:\n",
    "                unique_nums += 1\n",
    "        \n",
    "\n",
    "        keys = []\n",
    "        for x, c in enumerate(count):\n",
    "            if c > 0:\n",
    "                keys.append(x)\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(len(keys)):\n",
    "            a = keys[i]\n",
    "            T = target - a\n",
    "            left, right = i, len(keys) - 1\n",
    "            \n",
    "            while left <= right:\n",
    "                y, z = keys[left], keys[right]\n",
    "                \n",
    "                if y + z < T:\n",
    "                    left += 1\n",
    "                elif y + z > T:\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    if i < left < right:\n",
    "                        res += count[a] * count[y] * count[z]\n",
    "                    elif i == left < right:\n",
    "                        res += count[a] * (count[a] - 1) // 2 * count[z]\n",
    "                    elif i < left == right:\n",
    "                        res += count[a] * count[y] * (count[y] - 1) // 2\n",
    "                    else:\n",
    "                        res += count[a] * (count[a] - 1) * (count[a] - 2) // 6\n",
    "                    \n",
    "                    res %= MOD\n",
    "                    left += 1\n",
    "                    right -= 1\n",
    "        \n",
    "        return res % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        count = [0] * 101\n",
    "        unique_nums = 0\n",
    "        for num in arr:\n",
    "            count[num] += 1\n",
    "            if count[num] == 1:\n",
    "                unique_nums += 1\n",
    "        \n",
    "        keys = []\n",
    "        for num, cnt in enumerate(count):\n",
    "            if cnt > 0:\n",
    "                keys.append(num)\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(len(keys)):\n",
    "            a = keys[i]\n",
    "            T = target - a\n",
    "            left, right = i, len(keys) - 1\n",
    "            \n",
    "            while left <= right:\n",
    "                b, c = keys[left], keys[right]\n",
    "                \n",
    "                if b + c < T:\n",
    "                    left += 1\n",
    "                elif b + c > T:\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    if i < left < right: # a b c是不同的数字\n",
    "                        res += count[a] * count[b] * count[c]\n",
    "                    elif i == left < right: # a和b相同，c不同\n",
    "                        res += count[a] * (count[a] - 1) // 2 * count[c]\n",
    "                    elif i < left == right: # b和c相同，a不同\n",
    "                        res += count[a] * count[b] * (count[b] - 1) // 2\n",
    "                    else: # a b c相同\n",
    "                        res += count[a] * (count[a] - 1) * (count[a] - 2) // 6\n",
    "                    \n",
    "                    res %= MOD\n",
    "                    left += 1\n",
    "                    right -= 1\n",
    "        \n",
    "        return res % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        \"\"\"\n",
    "        arr[j] + arr[k] = target\n",
    "        arr[k] = target - arr[j]\n",
    "        \"\"\"\n",
    "        mp = defaultdict(int)\n",
    "        ans = 0\n",
    "        n = len(arr)\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(n):\n",
    "            mp.clear()\n",
    "            t = target - arr [i]\n",
    "            # print(ans)\n",
    "            for j in range(i + 1, n):\n",
    "                if t - arr[j] in mp:\n",
    "                    ans = (ans + mp[t - arr[j]]) % mod\n",
    "                mp[arr[j]] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def find_targe_sum(self, arr, idx, target, selected_num, total):\n",
    "        if idx==len(arr) and total<3:\n",
    "            return\n",
    "        if total==3:\n",
    "            S = 0\n",
    "            result = 1\n",
    "            for num, freq, selected in selected_num:\n",
    "                S += num*selected\n",
    "                result *= math.comb(freq, selected)\n",
    "            if S==target:\n",
    "                self.result = (self.result+result)%(1e9+7)\n",
    "                # print(selected_num, result)\n",
    "            return\n",
    "        num, freq = arr[idx]\n",
    "        self.find_targe_sum(arr, idx+1, target, selected_num, total)\n",
    "        for i in range(1, min(4-total, freq+1)):\n",
    "            selected_num.append((num, freq, i))\n",
    "            self.find_targe_sum(arr, idx+1, target, selected_num, total+i)\n",
    "            selected_num.pop(-1)\n",
    "        return\n",
    "        \n",
    "\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        arr = sorted(arr)\n",
    "        arr_tuple = {}\n",
    "        for num in arr:\n",
    "            if num not in arr_tuple:\n",
    "                arr_tuple[num] = 1\n",
    "            else:\n",
    "                arr_tuple[num] += 1\n",
    "        arr_tuple = list(arr_tuple.items())\n",
    "        self.result = 0\n",
    "        self.find_targe_sum(arr_tuple, 0, target, [], 0)\n",
    "        return int(self.result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        cnt = Counter(arr).most_common()\n",
    "        n = len(cnt)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                if i == j and cnt[i][1] < 2: continue\n",
    "                for k in range(j, n):\n",
    "                    if j == k and cnt[j][1] < 2: continue\n",
    "                    if i == j == k and cnt[i][1] < 3: continue\n",
    "                    if cnt[i][0] + cnt[j][0] + cnt[k][0] == target:\n",
    "                        if i == j == k:\n",
    "                            res += cnt[i][1] * (cnt[i][1] - 1) * (cnt[i][1] - 2) // 6 % MOD\n",
    "                        elif i == j and j != k:\n",
    "                            res += cnt[i][1] * (cnt[i][1] - 1) // 2 * cnt[k][1] % MOD\n",
    "                        elif i == k and j != k:\n",
    "                            res += cnt[i][1] * (cnt[i][1] - 1) // 2 * cnt[j][1] % MOD\n",
    "                        elif j == k and j != i:\n",
    "                            res += cnt[j][1] * (cnt[j][1] - 1) // 2 * cnt[i][1] % MOD\n",
    "                        else:\n",
    "                            res += cnt[i][1] * cnt[j][1] * cnt[k][1] % MOD\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        # 题意：问你从arr中任意选择三个数，这三个数相加的和等于target的组数有多少\n",
    "        # O（n**3)\n",
    "        mod = 10**9+7\n",
    "        ans = 0\n",
    "        arr.sort()\n",
    "        for i,x in enumerate(arr):\n",
    "            T = target - x\n",
    "            j,k = i+1,len(arr)-1\n",
    "\n",
    "            while j < k:\n",
    "                if arr[j] + arr[k] < T:\n",
    "                    j += 1\n",
    "                elif arr[j] + arr[k] > T:\n",
    "                    k -= 1\n",
    "                elif arr[j] != arr[k]:\n",
    "                    left = right = 1\n",
    "                    while j + 1 < k and arr[j] == arr[j+1]:\n",
    "                        left += 1\n",
    "                        j += 1\n",
    "                    while k - 1 > j and arr[k] == arr[k-1]:\n",
    "                        right += 1\n",
    "                        k -= 1\n",
    "                    ans += left * right\n",
    "                    ans %= mod\n",
    "                    j += 1\n",
    "                    k -= 1\n",
    "                else:\n",
    "                    ans += (k-j+1)*(k-j)//2\n",
    "                    ans%mod\n",
    "                    break\n",
    "        return ans%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "      MOD=int(1e9+7)\n",
    "      arr.sort()\n",
    "      def twoSum(start:int,target:int):\n",
    "        nonlocal ret\n",
    "        end=len(arr)-1\n",
    "        while start<end:\n",
    "          if arr[start]+arr[end]<target:\n",
    "            start+=1\n",
    "          elif arr[start]+arr[end]>target:\n",
    "            end-=1\n",
    "          elif arr[start]!=arr[end]:\n",
    "            ss,ee=start,end\n",
    "            while arr[ss]==arr[start]:ss+=1\n",
    "            while arr[ee]==arr[end]:ee-=1\n",
    "            ret+=(ss-start)*(end-ee)\n",
    "            ret%=MOD\n",
    "            start,end=ss,ee\n",
    "          else:\n",
    "            same_len=end-start+1\n",
    "            ret+=same_len*(same_len-1)//2\n",
    "            ret%=MOD\n",
    "            break\n",
    "      ret=0\n",
    "      for i,num in enumerate(arr):\n",
    "        _target=target-num\n",
    "        if _target<2*num: break\n",
    "        twoSum(i+1,_target)\n",
    "      return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def threeSumMulti(self, A, target):\n",
    "        MOD = 10**9 + 7\n",
    "        count = Counter(A)\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        # All different\n",
    "        for x in range(101):\n",
    "            for y in range(x+1, 101):\n",
    "                z = target - x - y\n",
    "                if y < z <= 100:\n",
    "                    ans += count[x] * count[y] * count[z]\n",
    "                    ans %= MOD\n",
    "\n",
    "        # x == y\n",
    "        for x in range(101):\n",
    "            z = target - 2*x\n",
    "            if x < z <= 100:\n",
    "                ans += count[x] * (count[x] - 1) / 2 * count[z]\n",
    "                ans %= MOD\n",
    "\n",
    "        # y == z\n",
    "        for x in range(101):\n",
    "            if (target - x) % 2 == 0:\n",
    "                y = (target - x) // 2\n",
    "                if x < y <= 100:\n",
    "                    ans += count[x] * count[y] * (count[y] - 1) // 2\n",
    "                    ans %= MOD\n",
    "\n",
    "        # x == y == z\n",
    "        if target % 3 == 0:\n",
    "            x = target // 3\n",
    "            if 0 <= x <= 100:\n",
    "                ans += count[x] * (count[x] - 1) * (count[x] - 2) // 6\n",
    "                ans %= MOD\n",
    "        return int(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\r\n",
    "        ans = 0\r\n",
    "        arr = sorted(arr)\r\n",
    "        n = len(arr)\r\n",
    "        for first in range(n):\r\n",
    "            second,third = first+1,n-1\r\n",
    "            while second<third:\r\n",
    "                sums = arr[first]+arr[second]+arr[third]\r\n",
    "                if sums==target:\r\n",
    "                    # ans+=1\r\n",
    "                    # second+=1\r\n",
    "                    if arr[second]==arr[third]:\r\n",
    "                        ans+=(third-second+1)*(third-second)/2\r\n",
    "                        break\r\n",
    "                    t1,t2 = 1,1\r\n",
    "                    while arr[second]==arr[second+1] and second+1<=third:\r\n",
    "                        t1+=1\r\n",
    "                        second+=1\r\n",
    "                    while arr[third]==arr[third-1] and third-1>=second:\r\n",
    "                        t2+=1\r\n",
    "                        third-=1\r\n",
    "                    ans+=(t1*t2)\r\n",
    "                    second+=1\r\n",
    "                    third-=1\r\n",
    "                elif sums>target:\r\n",
    "                    third-=1\r\n",
    "                else:\r\n",
    "                    second+=1\r\n",
    "        return int(ans%(10**9+7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        mp = Counter(arr)\n",
    "        keys = sorted(mp)\n",
    "        ans, n = 0, len(mp)\n",
    "\n",
    "        for i in range(n):\n",
    "            l, r = i, n-1\n",
    "            while l<=r:\n",
    "                tmpsum = keys[i] + keys[l] + keys[r]\n",
    "                # print('i:{}, l:{}, r:{}, ans:{}, sum:{}'.format(i, l, r, ans, tmpsum))\n",
    "                if tmpsum > target:\n",
    "                    r-=1\n",
    "                elif tmpsum < target:\n",
    "                    l+=1\n",
    "                else:\n",
    "                    cnt1, cnt2 = 0, 0\n",
    "                    def calcnt(n1, n2)->int:\n",
    "                        cnt1 = mp[keys[n1]]\n",
    "                        cnt2 = mp[keys[n2]]\n",
    "                        # print('cal before [{}, {}]'.format(cnt1,cnt2))\n",
    "                        if cnt1 == 1:\n",
    "                            cnt1 = 0\n",
    "                        elif cnt1 == 2:\n",
    "                            cnt1 = 1\n",
    "                        else: # 大于两个数，则进行组合，n选2\n",
    "                            cnt1 = comb(cnt1, 2) \n",
    "                        # print('calcnt({}, {}) -> {}'.format(n1, n2, cnt1*cnt2))\n",
    "                        return cnt1 * cnt2\n",
    "                    if (i == l and l != r): # 左边两个是同一个数\n",
    "                        ans += calcnt(i, r)\n",
    "                    elif (i!=l and l==r): # 右边两个是同一个数\n",
    "                        ans += calcnt(r, i)\n",
    "                    elif i!=l and l!=r: # 指向个不相同\n",
    "                        ans += mp[keys[i]] * mp[keys[l]] * mp[keys[r]]\n",
    "                    else: # 三个指针都指向同一个数\n",
    "                        # print('i : {}, l : {}, r : {}'.format(i,l,r))\n",
    "                        cnt1 = mp[keys[i]]\n",
    "                        if cnt1 < 3:\n",
    "                            cnt1 = 0\n",
    "                        elif cnt1 == 3:\n",
    "                            cnt1 = 1\n",
    "                        else:\n",
    "                            cnt1 = comb(cnt1, 3)\n",
    "                        ans += cnt1\n",
    "                    l+=1 # 哪个指针移动都可以，但是一定要移动\n",
    "\n",
    "\n",
    "        return ans % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "\n",
    "        count = Counter(arr)\n",
    "        keys = sorted(count) \n",
    "        len_distinct = len(keys)\n",
    "        res = 0\n",
    "\n",
    "        for left in range(len_distinct):\n",
    "            mid = left\n",
    "            right = len_distinct-1\n",
    "\n",
    "            while mid <= right:\n",
    "                cur_sum = keys[left] + keys[mid] + keys[right]\n",
    "                # print(left, mid, right)\n",
    "\n",
    "                if cur_sum == target:\n",
    "                    if left < mid < right:\n",
    "                        res += count[keys[left]] * count[keys[mid]] * count[keys[right]]\n",
    "                    elif left == mid < right:\n",
    "                        res += count[keys[left]] * (count[keys[mid]] - 1) / 2 * count[keys[right]]\n",
    "                    elif left < mid == right:\n",
    "                        res += count[keys[left]] * count[keys[mid]] * (count[keys[right]] - 1) / 2\n",
    "                    else:  # i == j == k\n",
    "                        res += count[keys[left]] * (count[keys[mid]] - 1) * (count[keys[right]] - 2) / 6\n",
    "                    # print(keys[left], keys[mid], keys[right])\n",
    "                    right -= 1\n",
    "                    mid += 1\n",
    "\n",
    "                if cur_sum > target:\n",
    "                    right -= 1\n",
    "\n",
    "                if cur_sum < target:\n",
    "                    mid += 1\n",
    "\n",
    "        return int(res % mod)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        c = Counter(arr)\n",
    "        hashSet = set()\n",
    "        res = 0\n",
    "        for i in c:\n",
    "            for j in c:\n",
    "                k = target -i -j\n",
    "                if k in c:\n",
    "                    if \" \".join([str(s) for s in sorted([i,j,k])]) in hashSet:\n",
    "                        continue\n",
    "                    if i == j == k and c[i] >=3:\n",
    "                        res += math.comb(c[i], 3)\n",
    "                    elif i == j != k and c[i] >= 2:\n",
    "                        res += math.comb(c[i], 2) * c[k]\n",
    "                    elif i == k != j and c[i] >= 2:\n",
    "                        res += math.comb(c[i], 2) * c[j]\n",
    "                    elif j == k != i and c[j] >= 2:\n",
    "                        res += math.comb(c[j], 2) * c[i]\n",
    "                    elif i != j != k:\n",
    "                        res += c[i] * c[j] * c[k]\n",
    "                    res %= 10 ** 9 + 7\n",
    "                    hashSet.add(\" \".join([str(s) for s in sorted([i,j,k])]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def threeSumMulti(self, A, target):\n",
    "        MOD = 10**9 + 7\n",
    "        count = collections.Counter(A)\n",
    "        print(count)\n",
    "        keys = sorted(count)\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        # Now, let's do a 3sum on \"keys\", for i <= j <= k.\n",
    "        # We will use count to add the correct contribution to ans.\n",
    "        for i, x in enumerate(keys):\n",
    "            T = target - x\n",
    "            j, k = i, len(keys) - 1\n",
    "            while j <= k:\n",
    "                y, z = keys[j], keys[k]\n",
    "                if y + z < T:\n",
    "                    j += 1\n",
    "                elif y + z > T:\n",
    "                    k -= 1\n",
    "                else: # x+y+z == T, now calculate the size of the contribution\n",
    "                    if i < j < k:\n",
    "                        ans += count[x] * count[y] * count[z]\n",
    "                    elif i == j < k:\n",
    "                        ans += count[x] * (count[x] - 1) / 2 * count[z]\n",
    "                    elif i < j == k:\n",
    "                        ans += count[x] * count[y] * (count[y] - 1) / 2\n",
    "                    else:  # i == j == k\n",
    "                        ans += count[x] * (count[x] - 1) * (count[x] - 2) / 6\n",
    "\n",
    "                    j += 1\n",
    "                    k -= 1\n",
    "\n",
    "        return int(ans % MOD)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        cnt = Counter()\n",
    "        for i in arr:\n",
    "            cnt[i]+=1\n",
    "        mod = 1000000007\n",
    "        res = 0\n",
    "        for i in range(1, target):\n",
    "            for j in range(i):\n",
    "                if target-j-i<=i:\n",
    "                    break\n",
    "                res+=cnt[j]*cnt[i]*cnt[target-i-j]\n",
    "                res%=mod\n",
    "                print(i, j, target-i-j, res)\n",
    "        for i in range(target//2+1):\n",
    "            if cnt[i]<2:\n",
    "                continue\n",
    "            if target == 3*i:\n",
    "                res+=cnt[i]*(cnt[i]-1)*(cnt[i]-2)//6 if cnt[i]>=3 else 0\n",
    "            else:\n",
    "                res+=(cnt[i]-1)*cnt[i]//2*cnt[target-2*i]\n",
    "            res = res%mod\n",
    "        \n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        m=len(arr)\n",
    "        tmdb=[]\n",
    "        B=dict()\n",
    "        for i in range(m):\n",
    "            if arr[i] not in B.keys():\n",
    "                B[arr[i]]=1\n",
    "                tmdb.append(arr[i])\n",
    "            else:\n",
    "                B[arr[i]]+=1\n",
    "        res=0\n",
    "        tmdnk=len(tmdb)\n",
    "        tmdb.sort()\n",
    "        # 3\n",
    "        if tmdnk>=1:\n",
    "            for each in tmdb:\n",
    "                if each*3==target and B[each]>=3:\n",
    "                    res+=B[each]*(B[each]-1)*(B[each]-2)//6\n",
    "            res=res%(10**9+7)\n",
    "        # 2\n",
    "        if tmdnk>=2:\n",
    "            for i in range(tmdnk):\n",
    "                for j in range(tmdnk):\n",
    "                    if tmdb[i]+2*tmdb[j]==target and B[tmdb[j]]>=2 and (tmdb[i]!=tmdb[j]):\n",
    "                        res+=B[tmdb[i]]*(B[tmdb[j]])*(B[tmdb[j]]-1)//2\n",
    "            res=res%(10**9+7)\n",
    "        # 1\n",
    "        if tmdnk>=3:\n",
    "            for i in range(tmdnk):\n",
    "                for j in range(i+1,tmdnk):\n",
    "                    if (target-tmdb[i]-tmdb[j] in tmdb) and target-tmdb[i]-tmdb[j] > tmdb[j] :\n",
    "                        print(target-tmdb[i]-tmdb[j],tmdb[j],tmdb[i])\n",
    "                        res+=B[tmdb[i]]*B[tmdb[j]]*B[target-tmdb[i]-tmdb[j]]\n",
    "            res=res%(10**9+7)\n",
    "        return res\n",
    "        \n",
    "\n",
    "\n",
    "                \n",
    "        \n",
    "\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from unittest import result\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr, target):\n",
    "        arr.sort()\n",
    "        cnt = 0\n",
    "        MOD = 10**9 + 7\n",
    "\n",
    "        for i in range(0, len(arr)):\n",
    "            left_p = i + 1\n",
    "            right_p = len(arr) - 1\n",
    "\n",
    "            while right_p > left_p:\n",
    "                if arr[i] + arr[left_p] + arr[right_p] == target: \n",
    "                    if arr[left_p] == arr[right_p]:\n",
    "                        cnt += (right_p - left_p) * (right_p - left_p + 1) / 2\n",
    "                        break\n",
    "                    else:\n",
    "                        l_c = 1\n",
    "                        r_c = 1\n",
    "                        while arr[left_p + 1] == arr[left_p]:\n",
    "                            l_c += 1\n",
    "                            left_p += 1\n",
    "                        \n",
    "                        while arr[right_p - 1] == arr[right_p]:\n",
    "                            r_c += 1\n",
    "                            right_p -= 1 \n",
    "                        \n",
    "                        cnt += l_c * r_c\n",
    "                        left_p += 1\n",
    "                        right_p -= 1\n",
    "                elif arr[i] + arr[left_p] + arr[right_p] > target:\n",
    "                    right_p -= 1\n",
    "                else:\n",
    "                    left_p += 1\n",
    "        \n",
    "        res = int(cnt) % MOD\n",
    "        return res\n",
    "            \n",
    "if __name__ == \"__main__\":\n",
    "    arr = [1,1,2,2,3,3,4,4,5,5]\n",
    "    target = 8\n",
    "    print(Solution().threeSumMulti(arr, target))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        # 固定住一个\n",
    "        ans = 0\n",
    "        a = 0 \n",
    "        \n",
    "        while a < len(arr)-2:\n",
    "            count_1 = 1\n",
    "            while a+1<len(arr) and arr[a]==arr[a+1]:\n",
    "                count_1 += 1\n",
    "                a += 1\n",
    "         \n",
    "       \n",
    "            b = a+1\n",
    "            c = len(arr)-1\n",
    "            count_2 = 0\n",
    "            count_3 = 0 \n",
    "            while b < c:\n",
    "                print(arr[a],arr[b],arr[c])\n",
    "                count_2 = max(1, count_2)\n",
    "                while b+1 < len(arr) and arr[b]==arr[b+1]:\n",
    "                    count_2 += 1\n",
    "                    b += 1\n",
    "              \n",
    "                if b>=c:\n",
    "                    break\n",
    "                count_3 = max(1, count_3)\n",
    "                while c > b + 1 and arr[c] == arr[c-1]:\n",
    "                    count_3 += 1\n",
    "                    c -= 1\n",
    "               \n",
    "\n",
    "                \n",
    "                if arr[a] + arr[b] + arr[c] == target:\n",
    "                    print(arr[a],arr[b],arr[c],count_1,count_2,count_3)\n",
    "                    ans += count_1*count_2*count_3\n",
    "                    ans %= 10**9 + 7\n",
    "                    b += 1\n",
    "                    c -= 1\n",
    "                    count_2 = 0\n",
    "                    count_3 = 0\n",
    "                elif arr[a] + arr[b] + arr[c] > target:\n",
    "                    c -= 1\n",
    "                    count_3 = 0\n",
    "                else:\n",
    "                    b += 1\n",
    "                    count_2 = 0\n",
    "            a += 1\n",
    "            \n",
    "        a=0\n",
    "        while a < len(arr):\n",
    "            count_1 = 1\n",
    "            while a+1<len(arr) and arr[a]==arr[a+1]:\n",
    "                count_1 += 1\n",
    "                a += 1\n",
    "         \n",
    "            if arr[a]+arr[a]+arr[a]==target:\n",
    "                #print(arr[a],count_1)\n",
    "                ans += count_1*(count_1-1)*(count_1-2)//6\n",
    "                ans %= 10**9 + 7\n",
    "            b = a+1\n",
    "            while b<len(arr):\n",
    "                count_2 = 1\n",
    "                while b < len(arr) - 1 and arr[b]==arr[b+1]:\n",
    "                    count_2 += 1\n",
    "                    b += 1\n",
    "                if arr[a]+arr[a]+arr[b]==target:\n",
    "                    #print(arr[a],arr[b],count_1,count_2)\n",
    "                    ans += count_1*(count_1-1)//2 *count_2 \n",
    "                    ans %= 10**9 + 7\n",
    "                if arr[a]+arr[b]+arr[b]==target:\n",
    "                    #print(arr[a],arr[b],count_1,count_2)\n",
    "                    ans += count_2*(count_2-1)//2 *count_1 \n",
    "                    ans %= 10**9 + 7\n",
    "                b+=1\n",
    "            a+=1\n",
    "                \n",
    "        return ans \n",
    "\n",
    "if __name__==\"__main__\":\n",
    "    ans = Solution().threeSumMulti([3,2,0,2],5)\n",
    "    print(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        mm=10**9+7\n",
    "        m=len(arr)\n",
    "        tmdb=[]\n",
    "        B=dict()\n",
    "        for i in range(m):\n",
    "            if arr[i] not in B.keys():\n",
    "                B[arr[i]]=1\n",
    "                tmdb.append(arr[i])\n",
    "            else:\n",
    "                B[arr[i]]+=1\n",
    "        res=0\n",
    "        tmdnk=len(tmdb)\n",
    "        tmdb.sort()\n",
    "        print(B)\n",
    "        # 3\n",
    "        if tmdnk>=1:\n",
    "            for each in tmdb:\n",
    "                if each*3==target and B[each]>=3:\n",
    "                    res+=B[each]*(B[each]-1)*(B[each]-2)//6\n",
    "            res=res%mm\n",
    "            print(res)\n",
    "        # 2\n",
    "        if tmdnk>=2:\n",
    "            for i in range(tmdnk):\n",
    "                for j in range(tmdnk):\n",
    "                    if tmdb[i]+2*tmdb[j]==target and B[tmdb[j]]>=2 and (tmdb[i]!=tmdb[j]):\n",
    "                        print(tmdb[i],tmdb[j])\n",
    "                        res+=B[tmdb[i]]*(B[tmdb[j]])*(B[tmdb[j]]-1)//2\n",
    "            res=res%mm\n",
    "            print(res)\n",
    "        # 1\n",
    "        if tmdnk>=3:\n",
    "            for i in range(tmdnk):\n",
    "                for j in range(i+1,tmdnk):\n",
    "                    if (target-tmdb[i]-tmdb[j] in tmdb) and target-tmdb[i]-tmdb[j] > tmdb[j] :\n",
    "                        print(target-tmdb[i]-tmdb[j],tmdb[j],tmdb[i])\n",
    "                        res+=B[tmdb[i]]*B[tmdb[j]]*B[target-tmdb[i]-tmdb[j]]\n",
    "            res=res%mm\n",
    "            print(res)\n",
    "        return res\n",
    "        \n",
    "\n",
    "\n",
    "                \n",
    "        \n",
    "\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        # M = 10**9 + 7\n",
    "        # ans = 0\n",
    "        # for i in range(len(arr)):\n",
    "        #     for j in range(i+1, len(arr)):\n",
    "        #         for k in range(j+1, len(arr)):\n",
    "        #             if arr[i] + arr[j] + arr[k] == target:\n",
    "        #                 ans += 1\n",
    "\n",
    "        # return ans % M\n",
    "        from collections import defaultdict\n",
    "        import bisect\n",
    "        M = 10 ** 9 + 7\n",
    "        ans = 0\n",
    "        dic = defaultdict(list)\n",
    "        for i in range(len(arr)):\n",
    "            for j in range(i+1, len(arr)):\n",
    "                dic[arr[i]+arr[j]].append(j)\n",
    "        for key in dic.keys():\n",
    "            dic[key] = sorted(dic[key])\n",
    "\n",
    "        for k in range(len(arr)):\n",
    "            if target - arr[k] in dic.keys():\n",
    "                # for index in dic[target - arr[k]]:\n",
    "                #     ans += 1 if k > index else 0\n",
    "                ans += bisect.bisect_left(dic[target-arr[k]], k)\n",
    "\n",
    "        return ans % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "#         cnt = Counter(arr)\n",
    "#         arr.sort()\n",
    "#         n = len(arr)\n",
    "#         mod = 10**9+7       \n",
    "#         ans = 0\n",
    "#         for i in range(n-2):\n",
    "#             cnt[arr[i]] -= 1\n",
    "#             g = cnt.copy()\n",
    "#             for j in range(i+1,n-1):\n",
    "#                 # print(g,cnt)\n",
    "#                 g[arr[j]] -= 1\n",
    "#                 t = target - arr[i] - arr[j]\n",
    "#                 if t < arr[0]:\n",
    "#                     break\n",
    "#                 ans += g[t]%mod\n",
    "#         return ans%mod\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        mod = 10**9+7 \n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,t,c):\n",
    "            if c == 0:\n",
    "                return t == 0\n",
    "            if i >= n or t < arr[i]:\n",
    "                return 0          \n",
    "            return (dfs(i+1,t-arr[i],c-1) + dfs(i+1,t,c))%mod      \n",
    "        return dfs(0,target,3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "#         cnt = Counter(arr)\n",
    "#         arr.sort()\n",
    "#         n = len(arr)\n",
    "#         mod = 10**9+7       \n",
    "#         ans = 0\n",
    "#         for i in range(n-2):\n",
    "#             cnt[arr[i]] -= 1\n",
    "#             g = cnt.copy()\n",
    "#             for j in range(i+1,n-1):\n",
    "#                 # print(g,cnt)\n",
    "#                 g[arr[j]] -= 1\n",
    "#                 t = target - arr[i] - arr[j]\n",
    "#                 if t < arr[0]:\n",
    "#                     break\n",
    "#                 ans += g[t]%mod\n",
    "#         return ans%mod\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        mod = 10**9+7 \n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,t,c):\n",
    "            # print(i,t,c)\n",
    "            if c == 0:\n",
    "                # print(t)\n",
    "                return t == 0\n",
    "            if i >= n or t < arr[i]:\n",
    "                return 0\n",
    "            \n",
    "\n",
    "            return (dfs(i+1,t-arr[i],c-1) + dfs(i+1,t,c))%mod\n",
    "            \n",
    "        \n",
    "        return dfs(0,target,3)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
